package leetcode.linked;

/**
 * K个一组翻转链表 困难
 */
public class Solution25 extends ListNode {
    //给定这个链表：1->2->3->4->5
    //当 k = 2 时，应当返回: 2->1->4->3->5
    //当 k = 3 时，应当返回: 3->2->1->4->5
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k <= 1) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pointer = dummy;

        while (pointer != null) {
            // 记录上一个子链表的尾
            ListNode lastGroup = pointer;

            int i = 0;
            for (; i < k; ++i) {
                pointer = pointer.next;
                if (pointer == null) {
                    break;
                }
            }

            // 如果当前子链表的节点数满足 k, 就进行反转
            // 反之，说明程序到尾了，节点数不够，不用反转
            if (i == k) {
                // 记录下一个子链表的头
                ListNode nextGroup = pointer.next;

                // 反转当前子链表，reverse 函数返回反转后子链表的头
                ListNode reversedList = reverse(lastGroup.next, nextGroup);

                // lastGroup 是上一个子链表的尾，其 next 指向当前反转子链表的头
                // 但是因为当前链表已经被反转，所以它指向的是反转后的链表的尾
                pointer = lastGroup.next;

                // 将上一个链表的尾连向反转后链表的头
                lastGroup.next = reversedList;

                // 当前反转后的链表的尾连向下一个子链表的头
                pointer.next = nextGroup;
            }
        }

        return dummy.next;
    }

    private ListNode reverse(ListNode head, ListNode tail) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode prev = null, temp = null;
        while ((head != null) && (head != tail)) {
            temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }

        return prev;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);

        ListNode listNode2 = new ListNode(2);
        listNode1.next = listNode2;

        ListNode listNode3 = new ListNode(3);
        listNode2.next = listNode3;

        ListNode listNode4 = new ListNode(4);
        listNode3.next = listNode4;

        listNode4.next = new ListNode(5, null);

        Solution25 solution25 = new Solution25();
        solution25.reverseKGroup(listNode1, 2);
    }
}
